package leetcode.editor.cn;

import java.util.Arrays;

/**
 * @id: 152
 * @title: 乘积最大子数组
 */
 
//给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 
//
// 示例 1: 
//
// 输入: [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 输入: [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
// Related Topics 数组 动态规划 
// 👍 1463 👎 0

public class P152MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new P152MaximumProductSubarray().new Solution();
        // todo
        final int[] ints = {0, 2,3,-2,4, -1};
        final int i = solution.maxProduct(ints);
        System.out.println(i);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
/*    public int maxProduct(int[] nums) {
        // 因为nums存在负数，所以当nums[i]为负数时，需要与dp[i]的最小值（负数）相乘
        // dp[i][0] max, dp[i][1] min
        int[][] dp = new int[nums.length][2];
        dp[0][0] = dp[0][1] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            // 不管nums[i]大于0或者小于0，都只需要获取最大值和最小值，本质不变
            dp[i][0] = Math.max(dp[i - 1][1] * nums[i], Math.max(dp[i - 1][0] * nums[i], nums[i]));
            dp[i][1] = Math.min(dp[i - 1][0] * nums[i], Math.min(dp[i - 1][1] * nums[i], nums[i]));
        }
        int ans = dp[0][0];
        for (int[] item: dp) {
            ans = Math.max(ans, item[0]);
        }
        return ans;
    }*/

    public int maxProduct(int[] nums) {
        // 滚动数组，压缩内存使用空间
        int max = nums[0], min = nums[0];
        int ans = nums[0];
        int mx, mn;
        for (int i = 1; i < nums.length; ++i) {
            // 由于java没有原子性的三变量最大值，所以需要使用额外一个变量
            mx = max;
            mn = min;
            max = Math.max(mn * nums[i], Math.max(mx * nums[i], nums[i]));
            min = Math.min(mx * nums[i], Math.min(mn * nums[i], nums[i]));
            ans = Math.max(max, ans);
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}